package sort

type InsertSort struct {
	BaseSort
}

// Sort 插入排序重点不是交换是插入
//func (self InsertSort) Sort() {
//	for i := 0; i < self.Len(); i++ {
//		for j := 0; j < i; j++ {
//			if self.Less(i, j) {
//				self.Swap(i, j)
//			}
//		}
//	}
//}
func (self InsertSort) Sort() {
	length := self.Len()
	array := self.Array
	for i := 1; i < length; i++ {
		temp := array[i]
		k := i - 1
		//寻找比索引i处小的数值
		for k >= 0 && self.Less(i, k) {
			k--
		}

		for j := i; j > k+1; j-- {
			array[j] = array[j-1]
		}
		array[k+1] = temp
	}
}

func (self InsertSort) Name() string {
	return "插入排序"
}
